<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      var mergeTrees = function (root1, root2) {
        // 方法一：递归（new 新的节点）
        // ---时间：O（min(m,n)）（其中 m 和 n 分别是两个二叉树的节点个数。
        // 对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作，
        // 因此被访问到的节点数不会超过较小的二叉树的节点数。）
        // ---空间：O（min(m,n)）（其中 mmm 和 nnn 分别是两个二叉树的节点个数。
        // 空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。）
        // if(!root1){
        //   return root2
        // }
        // if(!root2){
        //   return root1
        // }
        // const newTree = new TreeNode(root1.val+root2.val)
        // newTree.left = mergeTrees(root1.left,root2.left)
        // newTree.right = mergeTrees(root1.right,root2.right)
        // return newTree

        // 方法一：递归（复用旧节点）---时间：O（min(m,n)）---空间：O（min(m,n)）
        // if(!root1){
        //   return root2
        // }
        // if(!root2){
        //   return root1
        // }
        // root1.val += root2.val
        // root1.left = mergeTrees(root1.left,root2.left)
        // root1.right = mergeTrees(root1.right,root2.right)
        // return root1

        // 方法二：遍历（）---时间：O（min(m,n)）---空间：O（min(m,n)）
        const arr = [root1, root2];
        while (arr.length) {
          const right = arr.pop();
          const left = arr.pop();
          if (!right || !left) {
            return left ? left : right;
          }
          left.val += right.val;
          if (left.left && right.left) {
            arr.push(left.left);
            arr.push(right.left);
          } else if (right.left) {
            left.left = right.left;
          }
          if (left.right && right.right) {
            arr.push(left.right);
            arr.push(right.right);
          } else if (right.right) {
            left.right = right.right;
          }
        }
        return root1;
      };
    </script>
  </body>
</html>
